//
// Created by ASUS on 2024/3/20.
//
/*
给你一个整数数组 coins 表示不同面额的硬币，另给你一个整数 k 。
你有无限量的每种面额的硬币。但是，你 不能 组合使用不同面额的硬币。
返回使用这些硬币能制造的 第 kth 小 金额。
示例 1：
输入： coins = [3,6,9], k = 3
输出： 9
解释：给定的硬币可以制造以下金额：
3元硬币产生3的倍数：3, 6, 9, 12, 15等。
6元硬币产生6的倍数：6, 12, 18, 24等。
9元硬币产生9的倍数：9, 18, 27, 36等。
所有硬币合起来可以产生：3, 6, 9, 12, 15等。
示例 2：
输入：coins = [5,2], k = 7
输出：12
解释：给定的硬币可以制造以下金额：
5元硬币产生5的倍数：5, 10, 15, 20等。
2元硬币产生2的倍数：2, 4, 6, 8, 10, 12等。
所有硬币合起来可以产生：2, 4, 5, 6, 8, 10, 12, 14, 15等。
提示：
1 <= coins.length <= 15
1 <= coins[i] <= 25
1 <= k <= 2 * 109
coins 包含两两不同的整数。
 */
#include <bits/stdc++.h>
using namespace std;

long long findKthSmallest(vector<int>& coins, int k) {
	int n=coins.size();
	long long l=1,r=1LL*k*(*min_element(coins.begin(),coins.end()));
	while(l<=r){
		long long mid=l+(r-l)/2;
		long long res=0;
		for(int st=1;st<(1<<n);st++){
			long long lcmval=1;
			for(int i=0;i<n;i++){
				if((st>>i)&1) lcmval=lcm((long long)coins[i],lcmval);
			}
			if(__builtin_popcount(st)&1){
				res+=mid/lcmval;
			}else{
				res-=mid/lcmval;
			}
		}
		if(res>=k) r=mid-1;
		else l=mid+1;
	}
	return l;
}

int main(){
	return 0;
}